public class Solution1 {
    public int[] smallestK(int[] nums, int k){
        int[] ret = new int[k];
        //使用堆排序 - 建堆
        createHeap(nums, k);
        //将剩余的元素和堆顶元素比较 小于堆顶元素就交换下移，生成新的大根堆
        for(int i = k; i < nums.length; i++){
            if(nums[0] > nums[i]){
                swap(nums, 0, i);
                shiftDown(nums, 0, k);
            }
        }
        //复制数组
        for(int i = 0; i < k; i++){
            ret[i] = nums[i];
        }

        return ret;
    }
    private void createHeap(int[] nums, int len){
        //找最小的k个元素，要建立大根堆
        int parent = (len - 1 - 1) / 2;
        for(; parent >= 0; parent--){
            shiftDown(nums, parent, len);
        }
    }
    private void shiftDown(int[] nums, int parent, int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < len && nums[child] < nums[child + 1]){
                child++;
            }
            if(nums[child] > nums[parent]){
                swap(nums, parent, child);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }
    private void swap(int[] nums, int parent, int child){
        int tmp = nums[parent];
        nums[parent] = nums[child];
        nums[child] = tmp;
    }
}